package com.tianyuan.test2;

/**
 * 二维数组中的查找
 *
 * @date 2025/10/15 19:20
 * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个
 * 函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * [
 * [1,2,8,9],
 * [2,4,9,12],
 * [4,7,10,13],
 * [6,8,11,15]
 * ]
 * 给定 target =7，返回 true。
 * 给定 target =3，返回 false。
 * 数据范围：矩阵的长宽满足0≤n,m≤500，矩阵中的值满足-10的9次方≤ val ≤10的9次方
 */
import java.util.*;

public class Solution {
    /**
     * 在行列都递增的二维数组中查找目标值
     * @param target 要查找的目标整数
     * @param array 二维数组，每行从左到右递增，每列从上到下递增
     * @return 存在返回true，否则返回false
     */
    public boolean Find (int target, int[][] array) {
        // 遍历二维数组中的每一行
        for (int[] intArr : array) {
            // 检查当前行是否有元素，且该行第一个元素 <= 目标值
            // 因为数组每行递增，如果首元素都大于目标值，后续行首元素会更大，无需再查
            if (intArr.length > 0 && intArr[0] <= target) {
                // 对当前行执行二分查找（利用每行递增的特性）
                // Arrays.binarySearch返回值 >=0 表示找到目标
                if (Arrays.binarySearch(intArr, target) >= 0) {
                    return true; // 找到目标，直接返回true
                }
            } else {
                // 若当前行首元素 > 目标值，后续行无需检查，直接跳出循环
                break;
            }
        }
        // 所有符合条件的行都查找完毕仍未找到，返回false
        return false;
    }




    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例1测试
        int target1 = 7;
        int[][] array1 = {{1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
        boolean result1 = solution.Find(target1, array1);
        System.out.println("示例1返回值: " + result1); // 预期true

        // 示例2测试
        int target2 = 1;
        int[][] array2 = {{2}};
        boolean result2 = solution.Find(target2, array2);
        System.out.println("示例2返回值: " + result2); // 预期false

        // 示例3测试
        int target3 = 3;
        int[][] array3 = {{1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
        boolean result3 = solution.Find(target3, array3);
        System.out.println("示例3返回值: " + result3); // 预期false
    }
}
